Bernstein inequality

Let $X_1,X_2,...,X_k$ be independent random variables with each $X_i \in [-1,1]$. Let $\mu_i = \mathbb{E}[X_i]$ and $\sigma_i^2=\mathrm{Var}[X_i]$. Let $\mu=\sum_i \mu_i$ and $\sigma^2 = \sum_i \sigma_i^2$. Then, for $k \leq \frac{1}{2}\sigma$, $S=\sum_i X_i$ satisfies

Example of concentration inequality.

Special cases: Chernoff bound, Hoeffding inequality, Azuma’s Inequality

References:

• https://en.wikipedia.org/wiki/Bernstein_inequalities_(probability_theory)